package likou;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/11/13 10:08
 * dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-i-1]；
 */
public class _629 {
    public static void main(String[] args) {
        _629 o = new _629();
        System.out.println(o.kInversePairs(100, 3));
    }
    public int kInversePairs(int n, int k) {
        int[][] counts = new int[n][k + 1];
        counts[0][0] = 1;
        for (int i = 1; i < n; i++) {
            int left = 0;
            long sum = 0;
            for (int right = 0; right <= k; right++) {
                if (right - left > i) {
                    sum -= counts[i - 1][left];
                    left += 1;
                }
                sum += counts[i - 1][right];

                counts[i][right] = (int)(sum % 1000000007);
                if (sum == 0) {
                    break;
                }
            }
        }
        return counts[n - 1][k];
    }
}
